package hiepst.solution;

/**
 * Problem Statement
 * <P>
 * When a widget breaks, it is sent to the widget repair shop, which is capable
 * of repairing at most numPerDay widgets per day. Given a record of the number
 * of widgets that arrive at the shop each morning, your task is to determine
 * how many days the shop must operate to repair all the widgets, not counting
 * any days the shop spends entirely idle. For example, suppose the shop is
 * capable of repairing at most 8 widgets per day, and over a stretch of 5 days,
 * it receives 10, 0, 0, 4, and 20 widgets, respectively. The shop would operate
 * on days 1 and 2, sit idle on day 3, and operate again on days 4 through 7. In
 * total, the shop would operate for 6 days to repair all the widgets. Create a
 * class WidgetRepairs containing a method days that takes a sequence of arrival
 * counts arrivals (of type int[]) and an int numPerDay, and calculates the
 * number of days of operation.
 * </P>
 * 
 * Definition<BR>
 * Class: WidgetRepairs<BR>
 * Method: days<BR>
 * Parameters: int[], int<BR>
 * Returns: int<BR>
 * Method signature: int days(int[] arrivals, int numPerDay)<BR>
 * (be sure your method is public)<BR>
 * 
 * Limits<BR>
 * Time limit (s): 2.000<BR>
 * Memory limit (MB): 64<BR>
 * 
 * Constraints<BR>
 * - arrivals contains between 1 and 20 elements, inclusive.<BR>
 * - Each element of arrivals is between 0 and 100, inclusive.<BR>
 * - numPerDay is between 1 and 50, inclusive.<BR>
 * 
 * Examples<BR>
 * 
 * 0) { 10, 0, 0, 4, 20 }<BR>
 * 8<BR>
 * Returns: 6<BR>
 * The example above.<BR>
 * 
 * 1) { 0, 0, 0 }<BR>
 * 10<BR>
 * Returns: 0<BR>
 * 
 * 2) { 100, 100 }<BR>
 * 10<BR>
 * Returns: 20<BR>
 * 
 * 3) { 27, 0, 0, 0, 0, 9 }<BR>
 * 9<BR>
 * Returns: 4<BR>
 * 
 * 4) { 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6 }<BR>
 * 3<BR>
 * Returns: 15<BR>
 * 
 * <P>
 * This problem statement is the exclusive and proprietary property of TopCoder,
 * Inc. Any unauthorized use or reproduction of this information without the
 * prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003,
 * TopCoder, Inc. All rights reserved.
 * </P>
 * 
 * 
 * @author Hiep.Hong
 * 
 */

public class SRM150DIV2_WidgetRepairs {

	public int days(int[] arrivals, int numPerDay) {
		int days = 0;
		int carryOver = 0;
		for (int i = 0; i < arrivals.length; i++) {
			carryOver += arrivals[i];
			if (carryOver != 0) {
				carryOver = Math.max(0, carryOver - numPerDay);
				days++;
			}
		}

		return (int) (days + Math.ceil(carryOver / (double) numPerDay));
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SRM150DIV2_WidgetRepairs widgetRepairs = new SRM150DIV2_WidgetRepairs();
		int days = widgetRepairs.days(new int[] { 10, 0, 0, 4, 20 }, 8);
		System.out.println("days = " + days);

		days = widgetRepairs.days(new int[] { 0, 0, 0 }, 10);
		System.out.println("days = " + days);

		days = widgetRepairs.days(new int[] { 100, 100 }, 10);
		System.out.println("days = " + days);

		days = widgetRepairs.days(new int[] { 27, 0, 0, 0, 0, 9 }, 9);
		System.out.println("days = " + days);

		days = widgetRepairs.days(new int[] { 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3,
				4, 5, 6 }, 3);
		System.out.println("days = " + days);
	}

}
